home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / cmplrtut.arc / RXCOMP.C < prev    next >
Encoding:
Text File  |  1990-06-29  |  15.0 KB  |  435 lines
  1. /*  rxgrm.c */
  2. /*  REGULAR EXPRESSION GRAMMAR  */
  3. Goal
  4.   -> RegularExpression <eof>
  5. RegularExpression
  6.   -> AltExpr              => rx_emit  RXNT_ROOT
  7. AltExpr
  8.   -> RegExpr
  9.   -> AltExpr '|' RegExpr  => rx_emit  RXNT_ALT
  10. RegExpr
  11.   -> RXpr
  12.   -> ^ RXpr               => rx_emit  RXNT_RX_BEGIN
  13.   -> RXpr $               => rx_emit  RXNT_RX_END
  14.   -> ^ RXpr $             => rx_emit  RXNT_RX_BOTH
  15. RXpr
  16.   -> Span
  17.   -> RXpr Span            => rx_emit  RXNT_RX
  18. Span
  19.   -> TermList
  20.   -> Span .*              => rx_emit  RXNT_SPAN_0_FROM
  21.   -> Span .+              => rx_emit  RXNT_SPAN_1_FROM
  22.   -> .* TermList          => rx_emit  RXNT_SPAN_0_TO
  23.   -> .+ TermList          => rx_emit  RXNT_SPAN_1_TO
  24.   -> Span .* TermList     => rx_emit  RXNT_SPAN_0
  25.   -> Span .+ TermList     => rx_emit  RXNT_SPAN_1
  26. TermList
  27.   -> Term
  28.   -> TermList Term        => rx_emit  RXNT_TERM_LIST
  29. Term
  30.   -> Primary *            => rx_emit  RXNT_STAR
  31.   -> Primary +            => rx_emit  RXNT_PLUS
  32.   -> Primary ?            => rx_emit  RXNT_BIN
  33.   -> Primary
  34.   -> .                    => rx_emit  RXNT_ANY_C
  35. Primary
  36.   -> Char
  37.   -> <esc>                => rx_emit  RXNT_ESC_C
  38.   -> ( AltExpr )
  39.   -> [ ClassList ]        => rx_emit  RXNT_CLASS
  40.   -> [^ ClassList ]       => rx_emit  RXNT_NOT_CLASS
  41. ClassList
  42.   -> ClassItem
  43.   -> ClassList ClassItem  => rx_emit  RXNT_CLASS_LIST
  44. ClassItem
  45.   -> Char - Char          => rx_emit  RXNT_RANGE
  46.   -> Char
  47.   -> <esc>                => rx_emit  RXNT_ESC_C
  48. Char  -> <c>              => rx_emit  RXNT_C
  49.  
  50. /*  rx.h */
  51. /*  RX.H -- Header file for regular expression processing   */
  52. #define  SPACE        ' '
  53. #define  TAB          '\t'
  54. #define  NL           '\n'
  55. #define  NULLP        (char *) 0
  56. #define  AND          &&
  57. #define  OR           ||
  58. #define  BACK_SLASH   '\\'
  59. #define  isoctal(x)   ((x) >= '0'  AND  (x) <= '7')
  60. typedef enum {
  61.   ERROR_TOK,     EOF_TOK,      BEGIN_TOK,    /* --- Token Types --- */
  62.   END_TOK,       ALT_TOK,      CHAR_TOK,
  63.   ANY_CHAR_TOK,  ESCAPE_TOK,   LPAREN_TOK,
  64.   RPAREN_TOK,    LBRACKET_TOK, NOT_TOK,
  65.   RBRACKET_TOK,  STAR_TOK,     PLUS_TOK,
  66.   BIN_TOK,       DASH_TOK,     SPAN0_TOK,
  67.   SPAN1_TOK,
  68.   RXNT_ROOT,          /* --- Node Types --- */
  69.   RXNT_RX,            RXNT_RX_BEGIN,   RXNT_RX_END,
  70.   RXNT_RX_BOTH,       RXNT_SPAN_0,     RXNT_SPAN_1,
  71.   RXNT_SPAN_0_TO,     RXNT_SPAN_1_TO,  RXNT_SPAN_0_FROM,
  72.   RXNT_SPAN_1_FROM,   RXNT_ALT,        RXNT_TERM_LIST,
  73.   RXNT_STAR,          RXNT_PLUS,       RXNT_BIN,
  74.   RXNT_C,             RXNT_ANY_C,      RXNT_ESC_C,
  75.   RXNT_RANGE,         RXNT_CLASS,      RXNT_CLASS_LIST,
  76.   RXNT_NOT_CLASS
  77. }  RX_SYM;
  78. typedef struct RX_NODE  {           /* --- REG EXPR NODE --- */
  79.   RX_SYM   type;                    /* Node type (see above) */
  80.   char     c;                       /* Character */
  81.   char     flag;                    /* Flags: */
  82. #define      RX_BEGIN    0x01       /*   Match beginning of field */
  83. #define      RX_END      0x02       /*   Match end of field */
  84.   struct RX_NODE *lnode;            /* Ptr to left-node */
  85.   struct RX_NODE *rnode;            /* Ptr to right-node */
  86. }  RXNODE;
  87. #define  RXNODE_0   (RXNODE *) 0
  88. #ifdef  RXTRNL        /* rx_main has this #define'd.  So has definitions */
  89.   char   *token;                    /* Ptr to curr token. */
  90.   char   *input;                    /* Ptr to char after curr token. */
  91.   char   *T_beg;                    /* token-begin ptr */
  92.   char   *T_end;                    /* token-end ptr */
  93.   RXNODE *rx_root = (RXNODE *) 0;   /* Ptr to root node. */
  94.   int     rx_match_pos = -1;        /* Position of match. */
  95.   int     rx_match_len = -1;        /* Length of match. */
  96. #else            /* Other modules just contain declarations */
  97.   extern char   *input, *token, *T_beg, *T_end;
  98.   extern RXNODE *rx_root;
  99.   extern int     rx_match_pos, rx_match_len;
  100. #endif   /* RXTRNL */
  101. int  rx_parse      (char *);        /* --- Func Declarations --- */
  102. void rx_print_tree (RXNODE *, int);
  103. int  rx_match      (RXNODE *, char *);
  104. int  rx_scan       (void);
  105.  
  106. /* rx_main.c */
  107. /* RX_MAIN.C -- Driver program for the compiler  */
  108. #define  RXTRNL
  109. #include <string.h>
  110. #include <stdio.h>
  111. #include <dir.h>
  112. #include <dos.h>
  113. #include <rx.h>    /* globals defined here because RXTRNL is #define'd */
  114. int  main (int argc, char **argv)
  115. {
  116.   int    i, rc, match_sw, lin;
  117.   FILE  *stream;
  118.   char  *rx, *cp;
  119.   char   txt [258];
  120.   struct ffblk ffblk;    /* For Turbo C "findfirst" & "findnext" functions. */
  121.   if (argc != 3)  {
  122.     printf ("RX.EXE ----- Usage is:\n");
  123.     printf ("  RX \"<regexpr>\" <filemask>\n");
  124.     printf ("Where <regexpr> is a regular expression, in double quotes.\n");
  125.     printf ("And <filemask> is a DOS filename specification, wildcards OK.\n");
  126.     exit (8);
  127.   }
  128.   rx = argv[1];
  129.   i = rx_parse (rx);        /* Parse the reg. expr. */
  130.   if (i)  {
  131.     printf ("Parser error = %d\n", i);
  132.     exit (4);
  133.   }
  134.   printf ("RegExpr ==> \"%s\"\n", rx);
  135.   rc = findfirst (argv[2], &ffblk, 0);
  136.   while (rc == 0)  {        /* Try to match lines */
  137.     match_sw = 0;
  138.     lin = 1;
  139.     stream = fopen (ffblk.ff_name, "r");
  140.     if (stream == (FILE *) 0)  {
  141.       printf ("RX.EXE ----- Error OPENing data file '%s'.\n",
  142.       strupr(ffblk.ff_name));
  143.       exit(4);
  144.     }
  145.     printf ("File:  %s\n", strupr(ffblk.ff_name));
  146.     txt[0]=0;
  147.     while (fgets (txt+1, 256, stream) != 0)  {
  148.       if ((cp = strchr (txt+1, NL)) != NULLP)
  149.          *cp = 0;
  150.       /* ----- Attempt to match the reg.expr. ----- */
  151.       if (rx_match (rx_root, txt+1))  {
  152.          match_sw = 1;
  153.          printf ("%3d| %s\n", lin, txt+1);
  154.       }
  155.       lin++;
  156.     }
  157.     fclose (stream);
  158.     if (!match_sw)
  159.       printf ("No match occurred.\n");
  160.     rc = findnext (&ffblk);
  161.   }
  162.   return;
  163. }
  164.  
  165. /* rx_scan.c */
  166. /* RX_SCAN -- Lexical analyzer for regular expressions  */
  167. #include <ctype.h>
  168. #include <rx.h>
  169. static int in_brackets = 0;       /* In class brackets ? */
  170. int  rx_scan  (void)
  171. {
  172.   token=input;
  173.   switch (*input++)  {
  174.     case 0:
  175.     case NL:  return EOF_TOK;
  176.     case '^': if (in_brackets)  return CHAR_TOK;
  177.               return BEGIN_TOK;
  178.     case '$': if (in_brackets)  return CHAR_TOK;
  179.           return END_TOK;
  180.     case '.': if (in_brackets)  return CHAR_TOK;
  181.           if (*input=='*')  { ++input; return SPAN0_TOK; }
  182.           if (*input=='+')  { ++input; return SPAN1_TOK; }
  183.           return ANY_CHAR_TOK;
  184.     case '[': ++in_brackets;
  185.           if (*input=='^')  { ++input;  return NOT_TOK; }
  186.           else              { return LBRACKET_TOK;  }
  187.     case ']': --in_brackets; return RBRACKET_TOK;
  188.     case '|': if (in_brackets)  return CHAR_TOK;
  189.               return ALT_TOK;
  190.     case '(': if (in_brackets)  return CHAR_TOK;
  191.            return LPAREN_TOK;
  192.     case ')': if (in_brackets)  return CHAR_TOK;
  193.           return RPAREN_TOK;
  194.     case '*': if (in_brackets)  return CHAR_TOK;
  195.           return STAR_TOK;
  196.     case '+': if (in_brackets)  return CHAR_TOK;
  197.           return PLUS_TOK;
  198.     case '-': if (in_brackets
  199.               AND isalnum(*(input-2))
  200.           AND isalnum(*input))
  201.             return DASH_TOK;
  202.           return CHAR_TOK;
  203.     case '?': if (in_brackets)  return CHAR_TOK;
  204.           return BIN_TOK;
  205.     case BACK_SLASH:
  206.      if (*input=='b'  OR  *input=='f'  OR  *input=='n'
  207.      OR  *input=='r'  OR  *input=='t')    /* Std escape sequences */
  208.        { ++input;  return ESCAPE_TOK;  }
  209.      if (isoctal(*input) AND isoctal(*(input+1))
  210.      AND isoctal(*(input+2)))        /* Octal number */
  211.        { input+=3;  return ESCAPE_TOK; }
  212.      ++input;                  /* Else, literal char */
  213.      ++token;
  214.      return CHAR_TOK;
  215.     default:
  216.      return CHAR_TOK;
  217.   }
  218. }
  219.  
  220. /* rx_emit.c */
  221. /* RX_EMIT.C -- Emitter routines for abstract syntax tree.  */
  222. #include <rx.h>
  223. #define  RX_STK_SIZE      40               /* Arbitrary limits.  Should be */
  224. #define  RX_NUM_NODES    200               /*   enough for most cases, tho. */
  225. static RXNODE *rxstk [RX_STK_SIZE];        /* Semantic stack for reg expr. */
  226. static int     idx = -1;                   /* Index into semantic stack. */
  227. static RXNODE  rxnodearea [RX_NUM_NODES];  /* Stg for RXNODEs. */
  228. static RXNODE *rxnp = rxnodearea - 1;      /* Pointer to last used node. */
  229. static RXNODE *rxnp_max = rxnodearea + RX_NUM_NODES;   /* End of node area. */
  230. static RXNODE *make_rxnode (int, RXNODE *, RXNODE *);   /* Func Decl. */
  231. int rx_emit (int nodetype)
  232. {
  233.   char    c;
  234.   int     i;
  235.   RXNODE *np;
  236.   switch (nodetype)  {
  237.     case RXNT_ROOT:   rx_root = rxstk[idx];
  238.               break;
  239.     case RXNT_RX:
  240.     case RXNT_STAR:
  241.     case RXNT_PLUS:
  242.     case RXNT_BIN:
  243.     case RXNT_CLASS:
  244.     case RXNT_NOT_CLASS:
  245.      /* --- The single line of code below does it all!   1). Create a new
  246.         node.  2). Pop the top node pointer off the semantic stack.
  247.         3). Attach it as the new node's left-node pointer.  4). Push
  248.         pointer to new node onto the stack.  */
  249.      rxstk[idx] = make_rxnode (nodetype, rxstk[idx], RXNODE_0);
  250.      break;
  251.     case RXNT_RX_BEGIN:
  252.     case RXNT_RX_END:
  253.     case RXNT_RX_BOTH:
  254.      rx_emit (RXNT_RX);    /* Note node-type changed to RXNT_RX */
  255.      if (nodetype == RXNT_RX_BEGIN
  256.      OR  nodetype == RXNT_RX_BOTH)
  257.        rxstk[idx]->flag |= RX_BEGIN;
  258.      if (nodetype == RXNT_RX_END
  259.      OR  nodetype == RXNT_RX_BOTH)
  260.        rxstk[idx]->flag |= RX_END;
  261.      break;
  262.     case RXNT_ALT:
  263.     case RXNT_TERM_LIST:
  264.     case RXNT_CLASS_LIST:
  265.     case RXNT_RANGE:
  266.     case RXNT_SPAN_0:
  267.     case RXNT_SPAN_1:
  268.      rxstk[idx-1] = make_rxnode (nodetype, rxstk[idx-1], rxstk[idx]);
  269.      --idx;
  270.      break;
  271.     case RXNT_SPAN_0_TO:
  272.     case RXNT_SPAN_1_TO:
  273.      rxstk[idx] = make_rxnode (nodetype, RXNODE_0, rxstk[idx]);
  274.      break;
  275.     case RXNT_SPAN_0_FROM:
  276.     case RXNT_SPAN_1_FROM:
  277.      rxstk[idx] = make_rxnode (nodetype, rxstk[idx], RXNODE_0);
  278.      break;
  279.     case RXNT_C:
  280.      rxstk[++idx] = make_rxnode (nodetype, RXNODE_0, RXNODE_0);
  281.      rxstk[idx]->c = *T_beg;     /* Parser maintains "T_beg". */
  282.      break;
  283.     case RXNT_ANY_C:
  284.      rxstk[++idx] = make_rxnode (nodetype, RXNODE_0, RXNODE_0);
  285.      break;
  286.     case RXNT_ESC_C:     /* Note node type changed to RXNT_C. */
  287.      np = rxstk[++idx] = make_rxnode (RXNT_C, RXNODE_0, RXNODE_0);
  288.      c = *(T_beg+1);
  289.      if (c == 'b')  { np->c = '\b'; return 0; }
  290.      if (c == 'f')  { np->c = '\f'; return 0; }
  291.      if (c == 'n')  { np->c = '\n'; return 0; }
  292.      if (c == 'r')  { np->c = '\r'; return 0; }
  293.      if (c == 't')  { np->c = '\t'; return 0; }
  294.      if (isoctal(*(T_beg+1))
  295.      AND isoctal(*(T_beg+2))
  296.      AND isoctal(*(T_beg+3)))  {
  297.        i  = (*(T_beg+1) - '0') * 64;
  298.        i += (*(T_beg+2) - '0') * 8;
  299.        i +=  *(T_beg+3) - '0';
  300.        np->c = i;
  301.      }
  302.      else
  303.        np->c = *T_beg+1;
  304.      break;
  305.     default:  exit (3);     /* Something has gone wrong. */
  306.   }
  307.   if (idx >= RX_STK_SIZE)  {
  308.     printf ("Node-pointer stack overflow.\n");
  309.     exit (4);
  310.   }
  311.   return 0;
  312. }
  313. static RXNODE *make_rxnode (int type, RXNODE *lnode, RXNODE *rnode)
  314. {
  315.   if (++rxnp >= rxnp_max)  {        /* Alloc area for a new node */
  316.     printf ("Node area overflow\n");
  317.     exit (4);
  318.   }
  319.   rxnp->type = type;
  320.   rxnp->lnode = lnode;
  321.   rxnp->rnode = rnode;
  322.   rxnp->c = rxnp->flag = 0;
  323.   return (rxnp);
  324. }
  325.  
  326. /* rx_match.c */
  327. #include <string.h>
  328. #include <rx.h>
  329. static int match_node (RXNODE *, char *);     /* Local function */
  330. int  rx_match  (RXNODE *np, char *txt)
  331. {
  332.   int   i, j;
  333.   for (i=0; txt[i]; i++)  {
  334.     j = match_node (np, txt+i);
  335.     if (j >= 0)  {
  336.       rx_match_pos = i;          /* A MATCH !!! */
  337.       rx_match_len = j;
  338.       return 1;
  339.     }
  340.   }
  341.   rx_match_pos = -1;            /* No match. */
  342.   rx_match_len = -1;
  343.   return 0;
  344. }
  345. static int  match_node  (RXNODE *np, char *txt)
  346. {
  347.   int   i, j, n, dot;
  348.   if (np == (RXNODE *) 0)  return 0;
  349.   switch (np->type)  {
  350.     case RXNT_RX:            /* Must match both sub-nodes. */
  351.       if (np->flag & RX_BEGIN
  352.       AND *(txt-1) != 0)
  353.         return -1;
  354.          i = match_node (np->lnode, txt);
  355.          if (i<0)  return -1;
  356.          j = match_node (np->rnode, txt+i);
  357.          if (j<0)  return -1;
  358.       if (np->flag & RX_END
  359.       AND *(txt+i+j+1) != 0)
  360.         return -1;
  361.       return  i+j;
  362.     case RXNT_ALT:           /* Match if either subnode matches. */
  363.          i = match_node (np->lnode, txt);
  364.       j = match_node (np->rnode, txt);
  365.       return  i>j ? i : j;    /* Return the longer matching length. */
  366.     case RXNT_TERM_LIST:     /* Must match both subnodes. */
  367.          i = match_node (np->lnode, txt);
  368.          if (i<0)  return -1;
  369.          j = match_node (np->rnode, txt+i);
  370.          if (j<0)  return -1;
  371.          return i+j;
  372.     case RXNT_PLUS:     /* Must match 1 or more occurance(s) of left-node. */
  373.          i = match_node (np->lnode, txt);
  374.          if (i<0)  return -1;
  375.       /* ------ Fall into RXNT_STAR ----- */
  376.     case RXNT_STAR:     /* Match 0 or more occurance(s) of left-node. */
  377.       n = (np->type == RXNT_PLUS ? i : 0);   /* Account for fall-in. */
  378.       while (1)  {
  379.         i = match_node (np->lnode, txt+n);
  380.         if (i<=0)  return n;
  381.         n += i;
  382.       }
  383.     case RXNT_BIN:     /* Must match 0 or 1 occurance of left-node. */
  384.          i = match_node (np->lnode, txt);
  385.       return  i<0 ? 0 : i;
  386.     case RXNT_RANGE:         /* Must be in range, inclusive. */
  387.          return  (*txt < np->lnode->c  OR  *txt > np->rnode->c) ? -1 : 1;
  388.     case RXNT_CLASS:         /* Must match left-node. */
  389.          i = match_node (np->lnode, txt);
  390.       return  i>0 ? i : -1;
  391.     case RXNT_CLASS_LIST:    /* Must match either subnode. */
  392.          i = match_node (np->lnode, txt);
  393.          if (i>0)  return i;
  394.       j = match_node (np->rnode, txt);
  395.       if (j>0)  return j;
  396.          return -1;
  397.     case RXNT_NOT_CLASS:     /* Must not match left-node. */
  398.          i = match_node (np->lnode, txt);
  399.       return  i>0 ? -1 : 1;
  400.     case RXNT_SPAN_0:
  401.     case RXNT_SPAN_1:
  402.       i = match_node (np->lnode, txt);
  403.       if (i<0)  return -1;
  404.       if (i >= strlen(txt)  AND  np->type == RXNT_SPAN_1)
  405.         return -1;
  406.       dot = (np->type == RXNT_SPAN_1 ? 1 : 0);
  407.       for (n=strlen(txt+i+dot); n>=0; n--)  {
  408.         j = match_node (np->rnode, txt+i+dot+n);
  409.         if (j>=0)  return  i+dot+n+j;
  410.       }
  411.       return -1;
  412.     case RXNT_SPAN_0_TO:
  413.     case RXNT_SPAN_1_TO:
  414.       dot = (np->type == RXNT_SPAN_1_TO ? 1 : 0);
  415.       for (n=strlen(txt+dot); n>=0; n--)  {
  416.         i = match_node (np->rnode, txt+dot+n);
  417.         if (i>=0)  return dot+n+i;
  418.       }
  419.       return -1;
  420.     case RXNT_SPAN_0_FROM:
  421.     case RXNT_SPAN_1_FROM:
  422.       i = match_node (np->lnode, txt);
  423.       if (i<0)  return -1;
  424.       if (i >= strlen(txt)  AND  np->type == RXNT_SPAN_1_FROM)
  425.         return -1;
  426.       return strlen(txt);
  427.     case RXNT_C:        /* Must match the character. */
  428.       return  *txt == np->c ? 1 : -1;
  429.     case RXNT_ANY_C:     /* Matches anything except end-of-string. */
  430.       return  *txt ? 1 : -1;
  431.     default:    /* "I don't think we're in Kansas anymore, Toto." */
  432.          exit (1);
  433.   }
  434. }
  435.